<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Version vector</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Version_vector"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Version_vector rootpage-Version_vector skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Version vector</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><style data-mw-deduplicate="TemplateStyles:r1236090951">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Vector_clock" title="Vector clock">Vector clock</a>.</div>
<p>A <b>version vector</b> is a mechanism for tracking changes to data in a <a href="Distributed_system" class="mw-redirect" title="Distributed system">distributed system</a>, where multiple agents might update the data at different times. The version vector allows the participants to determine if one update preceded another (<a href="Happened-before" title="Happened-before">happened-before</a>), followed it, or if the two updates happened concurrently (and therefore might conflict with each other). In this way, version vectors enable <a href="Causality" title="Causality">causality</a> tracking among data replicas and are a basic mechanism for <a href="Optimistic_replication" title="Optimistic replication">optimistic replication</a>. In mathematical terms, the version vector generates a <a href="Preorder" title="Preorder">preorder</a> that tracks the events that precede, and may therefore influence, later updates.
</p><p>Version vectors maintain state identical to that in a <a href="Vector_clock" title="Vector clock">vector clock</a>, but the update rules differ slightly; in this example, replicas can either experience local updates (e.g., the user editing a file on the local node), or can synchronize with another replica:
</p>
<ul><li>Initially all vector counters are zero.</li>
<li>Each time a replica experiences a local update event, it increments its own counter in the vector by one.</li>
<li>Each time two replicas <span class="texhtml mvar" style="font-style:italic;">a</span> and <span class="texhtml mvar" style="font-style:italic;">b</span> synchronize, they both set the elements in their copy of the vector to the maximum of the element across both counters: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>V</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>a</mi>
</mrow>
</msub>
<mo stretchy="false">[</mo>
<mi>x</mi>
<mo stretchy="false">]</mo>
<mo>=</mo>
<msub>
<mi>V</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>b</mi>
</mrow>
</msub>
<mo stretchy="false">[</mo>
<mi>x</mi>
<mo stretchy="false">]</mo>
<mo>=</mo>
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>V</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>a</mi>
</mrow>
</msub>
<mo stretchy="false">[</mo>
<mi>x</mi>
<mo stretchy="false">]</mo>
<mo>,</mo>
<msub>
<mi>V</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>b</mi>
</mrow>
</msub>
<mo stretchy="false">[</mo>
<mi>x</mi>
<mo stretchy="false">]</mo>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}</annotation>
</semantics>
</math></span><img src="./edd5c158c15a0c45f4ffa677f78f6486a1acbf3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.359ex; height:2.843ex;" alt="{\displaystyle V_{a}[x]=V_{b}[x]=\max(V_{a}[x],V_{b}[x])}" loading="lazy"></span>. After synchronization, the two replicas have identical version vectors.</li></ul>
<p>Pairs of replicas, <span class="texhtml mvar" style="font-style:italic;">a</span>, <span class="texhtml mvar" style="font-style:italic;">b</span>, can be compared by inspecting their version vectors and determined to be either: identical (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
<mo>=</mo>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a=b}</annotation>
</semantics>
</math></span><img src="./1956b03d1314c7071ac1f45ed7b1e29422dcfcc4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a=b}" loading="lazy"></span>), concurrent (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\parallel b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
<mo>∥<!-- ∥ --></mo>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a\parallel b}</annotation>
</semantics>
</math></span><img src="./a15e706f9dcc819266c09e75020296d435959943.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.68ex; height:2.843ex;" alt="{\displaystyle a\parallel b}" loading="lazy"></span>), or ordered (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
<mo><</mo>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>
</semantics>
</math></span><img src="./91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy"></span> or <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
<mo><</mo>
<mi>a</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>
</semantics>
</math></span><img src="./ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy"></span>). The ordered relation is defined as: Vector <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
<mo><</mo>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>
</semantics>
</math></span><img src="./91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy"></span> if and only if every element of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{a}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>V</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>a</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V_{a}}</annotation>
</semantics>
</math></span><img src="./b26205fe6c67ed47c72959a921fe7fd9c1c250ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.457ex; height:2.509ex;" alt="{\displaystyle V_{a}}" loading="lazy"></span> is less than or equal to its corresponding element in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{b}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>V</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>b</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V_{b}}</annotation>
</semantics>
</math></span><img src="./47ede35aaff8460a086f9a2b6a787b163a3a5a30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.293ex; height:2.509ex;" alt="{\displaystyle V_{b}}" loading="lazy"></span>, and at least one of the elements is strictly less than. If neither <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
<mo><</mo>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>
</semantics>
</math></span><img src="./91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy"></span> or <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b<a}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
<mo><</mo>
<mi>a</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle b<a}</annotation>
</semantics>
</math></span><img src="./ec536027666ac731c00e6db3a3b0b10d7ebbe031.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle b<a}" loading="lazy"></span>, but the vectors are not identical, then the two vectors must be concurrent.
</p><p>Version vectors<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> or variants are used to track updates in many distributed file systems, such as <a href="Coda_(file_system)" title="Coda (file system)">Coda (file system)</a> and Ficus, and are the main data structure behind optimistic replication.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Other_mechanisms">Other mechanisms</h2></div>
<ul><li>Hash Histories <sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> avoid the use of counters by keeping a set of hashes of each updated version and comparing those sets by set inclusion. However this mechanism can only give probabilistic guarantees.</li>
<li>Concise Version Vectors <sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> allow significant space savings when handling multiple replicated items, such as in directory structures in filesystems.</li>
<li>Version Stamps <sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> allow tracking of a variable number of replicas and do not resort to counters. This mechanism can depict scalability problems in some settings, but can be replaced by Interval Tree Clocks.</li>
<li>Interval Tree Clocks<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> generalize version vectors and vector clocks and allows dynamic numbers of replicas/processes.</li>
<li>Bounded Version Vectors <sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> allow a bounded implementation, with bounded size counters, as long as replica pairs can be atomically synchronized.</li>
<li>Dotted Version Vectors <sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> address scalability with a small set of servers mediating replica access by a large number of concurrent clients.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Douglas Parker, Gerald Popek, Gerard Rudisin, Allen Stoughton, Bruce Walker, Evelyn Walton, Johanna Chow, David Edwards, Stephen Kiser, and Charles Kline. Detection of mutual inconsistency in distributed systems. Transactions on Software Engineering. 1983</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">David Ratner, Peter Reiher, and Gerald Popek. Dynamic version vector maintenance. Technical Report CSD-970022, Department of Computer Science, University of California, Los Angeles, 1997</span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">ByungHoon Kang, Robert Wilensky, and John Kubiatowicz.
The Hash History Approach for Reconciling Mutual Inconsistency.
ICDCS, pp. 670-677, IEEE Computer Society, 2003.</span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><a href="Dahlia_Malkhi" title="Dahlia Malkhi">Dahlia Malkhi</a> and Doug Terry. Concise Version Vectors in WinFS.Distributed Computing, Vol. 20, 2007.</span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Paulo Almeida, Carlos Baquero and Victor Fonte. Version Stamps: Decentralized Version Vectors. ICDCS, pp. 544-551, 2002.</span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Paulo Almeida, Carlos Baquero and Victor Fonte. Interval Tree Clocks. OPODIS, Lecture Notes in Computer Science, Vol. 5401, pp. 259-274, Springer, 2008.</span>
</li>
<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">José Almeida, Paulo Almeida and Carlos Baquero. Bounded Version Vectors. DISC: International Symposium on Distributed Computing, LNCS, 2004.</span>
</li>
<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Nuno Preguiça, Carlos Baquero, Paulo Almeida, Victor Fonte and Ricardo Gonçalves. Brief Announcement: Efficient Causality Tracking in Distributed Storage Systems With Dotted Version Vectors. ACM PODC, pp. 335-336, 2012.</span>
</li>
</ol></div></div>
<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>
<ul><li><a rel="nofollow" class="external text" href="http://queue.acm.org/detail.cfm?id=2917756">Why Logical Clocks are Easy (Compares Causal Histories, Vector Clocks and Version Vectors)</a></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2023-05-09" href="https://en.wikipedia.org/wiki/?title=Version_vector&oldid=1154045488">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>